package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/4/18 13:44
 */
public class C133 {

    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public static Node cloneGraph(Node node) {
        if(node == null) return null;
        Node ans = new Node(node.val), cur, cur1, oldNode, newNode;
        HashSet<Node> set = new HashSet<>();
        Queue<Node> q = new LinkedList<>(){{ add(node); add(ans); }};
        while (!q.isEmpty()) {
            cur = q.poll();
            cur1 = q.poll();
            for (int i = 0; i < cur.neighbors.size(); i++) {
                oldNode = cur.neighbors.get(i);
                if(!set.contains(oldNode)) {
                    newNode = new Node(oldNode.val);
                    cur1.neighbors.add(newNode);
                    q.add(oldNode);
                    q.add(newNode);
                }
                set.add(oldNode);
            }
        }
        return ans;
    }

    // for test
    public static void bfsPrint(Node node) {
        if(node == null) return;
        Node cur;
        HashSet<Node> set = new HashSet<>();
        Queue<Node> q = new LinkedList<>(){{ add(node); }};
        while (!q.isEmpty()) {
            cur = q.poll();
            for (int i = 0; i < cur.neighbors.size(); i++) {
                Node c = cur.neighbors.get(i);
                if(!set.contains(c)) {
                    System.out.print(cur+ " : " + c + "   ");
                    q.add(c);
                }
                set.add(c);
            }
            System.out.println();
        }
    }

    // for test
    public static void main(String[] args) {
        Node root = new Node(1);
        for (int i = 2; i <= 3; i++) {
            root.neighbors.add(new Node(i));
        }
        for (int i = 4; i <= 10; i++) {
            if(i <= 7) {
                root.neighbors.get(0).neighbors.add(new Node(i));
            }else {
                root.neighbors.get(1).neighbors.add(new Node(i));
            }
        }
        bfsPrint(root);
        bfsPrint(cloneGraph(root));

    }

}


